import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;


	public class DescendAlg {
		private ArrayList<Integer> DiffSet; //This variable should not be modified in any way!!!
		ArrayList<Integer> unused;
		public ArrayList<Integer> OriginalSet;
		private int peak = -1;
		int baseSize;
		

		public DescendAlg(ArrayList<Integer> ds) {
			DiffSet = ds; // Sorted set of differences
			DiffSet.trimToSize(); // memory conservation
			if (unsorted(ds)) {
				System.err.println("Unsorted set of differences!");
				Collections.sort(ds);
			}
			peak = DiffSet.get(DiffSet.size()-1);
			
			unused = (ArrayList<Integer>)DiffSet.clone();
			baseSize = (int)Math.floor(Math.sqrt(2*DiffSet.size()));
			OriginalSet = new ArrayList<>();
			LinkedList<Integer> list = FindSolution();
			Iterator<Integer> it = list.iterator();
			while (it.hasNext()) {
				OriginalSet.add((Integer)it.next());
			}
		}
		
		private boolean unsorted(ArrayList<Integer> ds) {
			Iterator<Integer> it = ds.iterator();
			int v = it.next();
			while (it.hasNext()) {
				int suc = it.next(); //successor
				if (suc < v) {
					return true;
				}
				v = suc;
			}
			return false;
		}
		
		private ArrayList<Integer> LinkedtoArrayList(LinkedList<Integer> ll) {
			ArrayList<Integer> al = new ArrayList<>();
			Iterator<Integer> it = ll.iterator();
			while (it.hasNext()) {
				al.add((Integer)it.next());
			}
			return al;
		}
		
		private LinkedList<Integer> FindSolution() {
			LinkedList<PartialRes> stack = new LinkedList<>();
			stack.add(new PartialRes(peak, (ArrayList<Integer>)DiffSet.clone(), new LinkedList<Integer>()));
			while (!stack.isEmpty()) {
				PartialRes pr = stack.pollFirst();
				if (pr.posBase.size() == baseSize) { 
					if (isResult(pr.posBase)) {
						return pr.posBase;
					} 
				} else {
					int index_desc = unused.indexOf(pr.decs);
					System.out.println(index_desc+" "+pr.decs);
//					Object o =  unused.subList(0, index_desc); 
//					if (o instanceof ArrayList<?> && (((ArrayList<?>) o).get(0) instanceof Integer)) {
//						
//						unused = (ArrayList<Integer>) o ;
//					} else {
//						System.err.println(o);
//						System.err.println("wrong sublisting");
//					}
					for (int i = unused.size() - 1; i > index_desc; i--) {
						unused.remove(i);
					}
					// trims unused set to elements lower than 
					unused.trimToSize();
					for (int i = 0; i < unused.size(); i++) {
						int elem = unused.get(i);  
						int compound =pr.decs - elem; // elem + compound = p.decs
						if (unused.indexOf(compound) == -1) {
							continue;
						}
						if (pr.decs - unused.get(i) < unused.get(i)) {
							break;
						}
						System.out.println(unused.indexOf(compound)+" "+unused.indexOf(elem));
						LinkedList<Integer> posBase1 = (LinkedList<Integer>) pr.posBase.clone();
						LinkedList<Integer> posBase2 = (LinkedList<Integer>) pr.posBase.clone();
						posBase1.addLast(compound);
						stack.addFirst(new PartialRes(elem, unused, posBase1));
						posBase2.addLast(elem);
						stack.addFirst(new PartialRes(compound, unused, posBase2));
						
					}
				}
			}
			return null;
		}
		
		private boolean isResult(LinkedList<Integer> b) { 
			int sum = 0;
			Iterator<Integer> it = b.iterator();
			while (it.hasNext()) {
				sum += (int)it.next();
			}
			if (sum != peak) {
				return false;
			}
			ArrayList<Integer> ds = (ArrayList<Integer>) DiffSet.clone();
			for (int i = 0; i < b.size(); i++) {
				for (int j = i; j < b.size(); j++) {
					int elem = 0;
					for (int k = i; k <= j; k++) {
						elem += b.get(k);
					}
					int index = ds.indexOf(elem);
					if (index == -1) {
						return false;
					} else {
						ds.remove(index);
					}
					
				}
			}
			return true;
		}
		
		private class PartialRes {
			int decs; // Element on which the recursion is done
			ArrayList<Integer> unused; // Unused elements that can be in base
			LinkedList<Integer> posBase; //possible base result
			public PartialRes(int desc, ArrayList<Integer> unused, LinkedList<Integer> posBase) {
				this.decs = desc;
				this.unused = unused;
				this.posBase = posBase;
			}
		}
}
